const treeObj = {
  key: 11,
  left: {
    key: 7,
    left: {
      key: 5,
      left: {
        key: 3,
        left: undefined,
        right: undefined,
      },
      right: {
        key: 6,
        left: undefined,
        right: undefined,
      },
    },
    right: {
      key: 9,
      left: {
        key: 8,
        left: undefined,
        right: undefined,
      },
      right: {
        key: 10,
        left: undefined,
        right: undefined,
      },
    },
  },
  right: {
    key: 15,
    left: {
      key: 13,
      left: {
        key: 12,
        left: undefined,
        right: undefined,
      },
      right: {
        key: 14,
        left: undefined,
        right: undefined,
      },
    },
    right: {
      key: 20,
      left: {
        key: 18,
        left: undefined,
        right: undefined,
      },
      right: {
        key: 25,
        left: undefined,
        right: undefined,
      },
    },
  },
};

// 中序遍历
// function cb(key) {
//   console.log(key);
// }

// function inOrderTraverse(node, callback) {
//   if (node.left != undefined) {
//     inOrderTraverse(node.left, callback);
//     callback(node.key);
//     inOrderTraverse(node.right, callback);
//   }
// }

// inOrderTraverse(treeObj, cb);

// 先序遍历
// function cb(key) {
//   console.log(key);
// }

// function inOrderTraverse(node, callback) {
//   if (node.left != undefined) {
//     callback(node.key);
//     inOrderTraverse(node.left, callback);
//     inOrderTraverse(node.right, callback);
//   }
// }

// inOrderTraverse(treeObj, cb);

// 后续遍历
// function cb(key) {
//   console.log(key);
// }

// function inOrderTraverse(node, callback) {
//   if (node.left != undefined) {
//     inOrderTraverse(node.right, callback);
//     inOrderTraverse(node.left, callback);
//     callback(node.key);
//   }
// }

// inOrderTraverse(treeObj, cb);

// 搜索特定的一个点
// function searchNode(node, key) {
//   if (!node.key) return false;
//   if (key < node.key) {
//     return searchNode(node.left, key);
//   } else if (key > node.key) {
//     return searchNode(node.right, key);
//   } else {
//     return true;
//   }
// }

// console.log(searchNode(treeObj, 3));
// console.log(searchNode(treeObj, 25));
// console.log(searchNode(treeObj, 111));
// console.log(searchNode(treeObj, 0));

// 获取最小
function minNode(node) {
  if (node.left) {
    return minNode(node.left);
  }
  return node;
}
// 获取最大
function maxNode(node) {
  if (node.right) {
    return maxNode(node.right);
  }
  return node;
}

// console.log(minNode(treeObj));
// console.log(maxNode(treeObj));

// 删除任意一项
// function removeNode(node, key) {
//   if (!node) return false;
//   if (key < node.key) {
//     return removeNode(node.left, key);
//   } else if (key > node.key) {
//     return removeNode(node.right, key);
//   }
//   if (!node.right && !node.left) {
//     node = undefined;
//     return node;
//   }
//   if (!node.right) {
//     node = node.left;
//     return node;
//   } else if (!node.left) {
//     node = node.right;
//     return node;
//   }
//   const dom = minNode(node.right);
//   node.key = dom.key;
//   node.right = removeNode(node.right, dom.key);
//   return node;
// }

// console.log(removeNode(treeObj, 3));
// console.log(removeNode(treeObj, 18));
// console.log(removeNode(treeObj, 20));
